# leetcode 53, 最大子数组和， 动态规划类型

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums) # dp[i]表示以第i个元素结尾的最长连续子序列的和
        dp[0] = nums[0]
        if len(nums) == 1:
            return nums[0]
        for i in range(1, len(nums) ):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
            # dp[i]可以由两个方向推出：
            # 第一，由dp[i-1] + num[i]推出
            # 第二，丢弃前面所有的结果，从nums[i]开始
            # 取二者之间的最大值作为dp[i]
        print(dp)
        return max(dp)
